public class Test{

    static int res = Integer.MAX_VALUE;
    public static int coinChange(int[] coins, int amount) {
        if(coins.length == 0){
            return -1;
        }

        Test.findWay(coins,amount,0);

        if(res == Integer.MAX_VALUE){
            return -1;
        }
        return res;
    }

    public static void findWay(int[] coins,int amount,int count){
        if(amount < 0){
            return;
        }
        if(amount == 0){
            res = Math.min(res,count);
        }

        for(int i = 0;i < coins.length;i++){
            findWay(coins,amount-coins[i],count+1);
        }
    }

    public static void main(String[] args){
        int res;
        int[] arr = {1,2,5,10,20,100};
        res = Test.coinChange(arr,250);
        System.out.println(res);
    }
}